BOJ27896 특별한 서빙

풀이

X[i]의 부호를 결정해서 어떤 prefix sum도 M미만이 되게 하는 최소 음수부호 개수를 구하는 문제입니다. 제일 절댓값이 큰 수부터 음수로 만들어주는게 떠오르지만 최적이 아닙니다. 그리디문제에서는 종종 경제학의 ‘옵션’개념을 도입하면 논리의 전개가 깔끔해지는 경우가 많습니다. 옵션은 추후의 상황에 따라 행사할 수도, 행사하지 않고 포기할 수도 있습니다. 지금 문제에서는 최대한 음수를 적게 써야하므로, 기본적으로 양수를 더해주고, 이후에 M미만을 만들기 위해 현재더했던 양수값을 음수로 바꿀 수 있는 옵션(+x[i]를 -x[i]로 바꿔야 하므로, 이 옵션은 불만도에 -2*x[i]를 더해주는것과 같음)을 획득하는것으로 생각할 수 있습니다. 이제 입력 순서대로 각 x[i]를 양수로 불만도에 더해가면서, 불만도가 M이상이 되었을때 현재까지 획득한 옵션중 불만도를 제일 크게 낮춰줄 수 있는 것(=최솟값)을 불만도가 M미만이 될때까지 행사해주면 됩니다. 심화: 보통 이런 옵션가지고 풀 수 있는 그리디는 MCMF로 모델링가능합니다. 이 때 옵션과 residual의 관계를 생각해보면 좋습니다. 코드: http://boj.kr/57ea9dbd3e76470f9aca35f66b5e6b7e